class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: list,
                                 blue_edges: list) -> list:
        RED = 1
        BLUE = -1
        WHITE = 0
        adj = [[] for _ in range(n)]
        ans = [-1 for _ in range(n)]
        for edge in red_edges:
            adj[edge[0]].append((edge[1], RED))
        for edge in blue_edges:
            adj[edge[0]].append((edge[1], BLUE))
        queue = [(0, WHITE)]
        layer = 0
        visited = set()
        visited.add((0, WHITE))
        while queue:
            for _ in range(len(queue)):
                cur, color = queue.pop(0)
                if ans[cur] < 0:
                    ans[cur] = layer
                for n, c in adj[cur]:
                    if (n, c) in visited:
                        continue
                    if c == color:
                        continue
                    queue.append((n, c))
                    visited.add((n, c))
            layer += 1
        return ans
